package ListNode;

import java.util.*;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public void levelHelper(ArrayList<ArrayList<Integer>> list,TreeNode root,int level){
        if(root==null)
            return ;
        if(level>=list.size()){
            list.add(new ArrayList<>());
        }
        list.get(level).add(root.val);
        levelHelper(list,root.left,level+1);
        levelHelper(list,root.right,level+1);
    }
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root){
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        int level=0;
        levelHelper(list,root,level);
        return list;
    }


    public ArrayList<ArrayList<Integer>> levelOrder2(TreeNode root){
        if(root==null)
            return null;
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            ArrayList<Integer> temp=new ArrayList<>();
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode node=queue.poll();
                temp.add(node.val);
                if(node.left!=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
            }
            list.add(temp);
        }

        return list;
    }
//左右顺序输出
    public  ArrayList<ArrayList<Integer>> levelOrder3(TreeNode root){
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        if(root!=null)
            queue.add(root);
        while(!queue.isEmpty()){
            ArrayList<Integer> temp=new ArrayList<Integer>();
            for(int i=queue.size();i>0;i--){
                TreeNode node=queue.poll();
                if((list.size()+1)%2==1){
                    temp.add(node.val);
                }else{
                    temp.add(0,node.val);
                }
                if(node.left!=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
            }
            list.add(temp);
        }

        return list;
    }

//三元数组
       public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
           Arrays.sort(num);
           if(num==null||num.length<3){
               return null;
           }
           for(int i=0;i<num.length-2;i++){
               if(num[i]>0)
                   break;
               if(i>0&&num[i]==num[i+1])
                   continue;
               int l=i+1;
               int r=num.length-1;
               while(l<r){
                   int sum=num[i]+num[l]+num[r];
                   if(sum==0){
                       ArrayList<Integer> temp=new ArrayList<>();
                       temp.add(num[i]);
                       temp.add(num[l]);
                       temp.add(num[r]);
                       list.add(temp);

                   while(l<r&&num[l]==num[l+1])
                       l++;
                   while(l>r&&num[r]==num[r-1])
                       r--;
                   l++;r--;
                   }else if(sum>0){
                       r--;
                   }else {
                       l++;
                   }
               }
           }

            return list;
       }
       public int getK(int[] a,int n,int K){
        Arrays.sort(a);
       ArrayList<Integer> list=new ArrayList<Integer>();
        for(int i=0;i<a.length;i++){
            if(!list.contains(a[i])){
                list.add(a[i]);
            }
        }
         return list.get(K);
       }
     //求数组子数组的最大的和
    public int maxsumofSubarray(int[] a){
        if(a.length==0){
            return 0;
        }
        int sum=a[0];
        int max=sum;
        for(int i=0;i<a.length;i++){
            sum=sum>0?sum+a[i]:a[i];
            max=Math.max(max,sum);
        }
        return max;
    }

    public int maxsumofSubarray2(int[] arr){
        if(arr.length == 0)return 0;
//初始化动态数组
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
//定义最大值
        int max = dp[0];
        for(int i = 1;i < arr.length;i++){
            if(dp[i-1] > 0)
                dp[i] = dp[i-1] + arr[i];
            else
                dp[i] = arr[i];
            max = Math.max(max,dp[i]);
        }
        return max;
    }
    public static void main(String[] args){
        /*TreeNode node=new TreeNode();
        node.val=1;
        TreeNode left=new TreeNode();
        left.val=2;
        TreeNode right=new TreeNode();
        right.val=3;
        node.left=left;
        node.right=right;
        System.out.print(node.levelOrder2(node));
        System.out.println(node.levelOrder(node));
        System.out.println(node.levelOrder3(node));*/

        int[] a={-2,0,1,1,2};
        ArrayList<ArrayList<Integer>> list=new TreeNode().threeSum(a);
        System.out.println(list);
    }

}
